package com.ss.question;

import com.ss.travelsal.MorrisTravelsal;

/**
 * 题目一：
 * 已知一个搜索二叉树后序遍历的数组 posArr，请根据 posArr，
 * 重建出整棵树，返回新建树的头节点。
 * @author 叁昇
 * @create 2021-02-28-16:29
 */
public class Que01_PosArrToBST {
    public static class Node {
        public int value;
        Node left;
        Node right;
        public Node(int data) {
            this.value = data;
        }
    }

    public static Node posArrToBST(int[] posArr){
        return process(posArr, 0, posArr.length - 1);
    }

    // TODO
    private static Node process(int[] posArr, int l, int r) {
        if (l > r) {
            return null;
        }
        Node head = new Node(posArr[r]);
        if (l == r) {
            return head;
        }
        int m = l - 1;
        for (int i = l; i < r; i++) {
            if (posArr[i] < posArr[r]) m = i;
        }
        head.left = process(posArr, l, m);
        head.right = process(posArr, m+1, r-1);
        return head;
    }
}
